\subsection{Complejidad algoritmo Prueba}

Para el algoritmo de probar primero se cicla toda la matriz del tablero de puntos así podemos saber cual posición esta ocupada y contar la cantidad de posiciones negras.
Acceder a la posición de la matriz es $O(1)$ y  comparar esa posición con un numero es $O(1)$, recorrer toda la matriz lleva $O(Base*Altura)$ siendo Base , Altura, miembros de la estructura tablero.

Luego se compara la cantidad de posiciones negras libres del tablero con la cantidad de posiciones negras de la ficha, acceder a los miembros de las estructuras lleva $O(1)$ y compararlos lleva $O(1)$

Por ultimo se recorren las posiciones que va a ocupar en el tablero la ficha y se va comparando el valor de la ficha con el de la posición del tablero, esto lleva en el peor caso $O(Base*Altura)$ siendo en este caso
Base y Altura miembros de la estructura de Ficha.

Complejidad Total: $O(Base*Altura)$ siendo base y altura los miembros de la estrctura tablero  


\subsection{Complejidad Algoritmo Rotar:}

Primero se toman las dimensiones de la matriz que representa la ficha, esto es en $O(1)$ porque se acceden a los miembros de la estructura Ficha.
Luego se recorre esa matriz copiando en una nueva cada punto empezando de atrás para adelante en las columnas e iterando sobre las filas, esto lleva $O(Base*Altura)$
Luego se copia en la otra estructura los nuevos valores.
Complejidad Total : $O(Base*Altura)$ Siendo Base y altura los miembros de la estructura de la fichas
    
Complejidad del algoritmos Actualizar:

Primero se recorre la matriz que representa el arreglo solo las posiciones donde va a ir la ficha asignándose la posición en la matriz para marcar que esta usada la posición esto cuesta $O(BASE*ALTURA)$ siendo 
Base y altura la base y altura de la ficha y la asignación del campo cuesta $O(1)$.

Luego se recorre el tablero desde la posición ultima posición marcada hasta la próxima libre, en el peor caso se recorre todo el tablero por lo tanto la complejidad es $O(BaseT*AlturaT)$ siendo 
BaseT y AlturaT la base y altura del tablero.

Complejidad Total:  $O(Base*Altura)$ porque la base y altura del tablero son mayores o igual a la de la ficha.


\subsection{Complejidad del algoritmo Desactualizar:}
En este algoritmo es muy parecido al de actualizar, primero se recorre la matriz del tablero en las posiciones que se va a colocar la ficha y esto cuesta $O(Base*Altura)$ de la ficha y en cada
posición pone un 0 esto cuesta $O(1)$ por ultimo se actualiza la ultima posicon del tablero eso cuesta $O(1)$.
Complejidad Total : $O(1)$

\subsection{Complejidad del algoritmo de Backtracking: }
Primero se cicla el vector de Fichas, vemos si para cada ficha la cantidad de posiciones que ocupa, osea base * altura, es mas grande que la cantidad de posiciones libres del tablero
y si la cantidad de posiciones negras de la ficha es mayor a la cantidad de posiciones negras del tablero, en caso este caso se borra la ficha.
 Tanto Acceder a los miembros de la estructura y compararlos lleva $O(1)$, recorrer todo el vector lleva $O(K)$ siendo K la cantidad de elementos del arreglo, osea cantidad de fichas.
Luego consultamos si la cantidad de posiciones libres que tiene el tablero es 0, acceder a el miembro $cantLibres$ de la estructura 
tablero nos lleva O(1) y la comparación es $O(1)$ a si como en el paso siguiente consultamos si la cantidad de fichas que nos queda para probar es igual a 0, nos lleva $O(1)$.
Por ultimo Comenzamos un ciclo sobre las fichas, vamos rotando la ficha , como maximo se rota cuatro veces antes de llamar al algoritmo probar vemos si no estamos en el borde comparando si a la posición
en la que estamos parados del tablero le sumamos la altura seguimos estando dentro del tablero al igual que con la base , al igual que con la altura esto lleva $O(1)$ y se llama al algoritmo Probar:\\
Si la funcion probar devuelve:\newline
\begin{itemize}
\item cero , entonces es la solución , se agrega la solución al vector de posiciones, esto lleva $O(1)$ las asignaciones y agregarlo también porque se agrega en el ultimo elemento y el backtracking devuelve verdadero \newline
\item uno , entonces faltan fichas por colocar y se agrega la posición al vector de posiciones esto lleva como en el caso anterior $O(1)$, se quita la ficha del vector de Fichas, y se llama al paso recursivo.\newline
	Si la misma devuelve verdadero entonces termina y termina el backtracking devolviendo la solución optima, en el caso contrario se saca del vector de posiciones la ultima ficha, se vuelve a agregar en\newline
\item dos, entonces se vuelve a rotar la ficha y sigo probando porque es un problema de colores.\newline
\item  tres, se sigue rotando la ficha a ver si hay solución.\newline
\end{itemize}

En caso contrario de que no entre la ficha porque estamos en un borde del tablero, llamamos a la función rotar y seguimos probando.

Para el backtracking el peor caso es que probemos todas las posibilidades, osea probar todas las fichas que tengamos en el fichero.
Por lo tanto como en la primer posición voy a probar N fichas , mas girar todas es 4N formas, ahora para cada 1 de esas tengo 4(N-1) formas de poner las fichas restantes, asi sucesivamente hasta llegar a la ultima ficha,
por lo tanto la complejidad nos quedaría T(N) = (4N)!. \newline
Sabemos que  $O(Base*Altura)$ $\in$  $O(4N!)$ sea la base y altura del tablero o de la ficha, y $O(N)$ $\in$ $O(4N!)$\newline

Por lo tanto la complejidad total del algoritmo de backtracking seria: $O(4N!)$  


	 

